﻿// 373. Raising Modulo Numbers（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
/*
https://www.papamelon.com/problem/373

给定一个整数M。

再给定一个整数H，接下来有H 对Ai,Bi。

求
(A1^B1+A2^B2+A3^B3+...+AH^BH) mod M。

输入
第一行一个整数
Z(1≤Z≤10)，表示有多少组测试数据
每组测试数据格式如下：
第一行是
M(1≤M≤45000)
第二行是
H(1≤H≤45000)
接下来H 行，每行两个整数，表示
Ai,Bi
​

Ai ,Bi不会同时为0
输出
每组测试数据输出一行，一个整数，表示计算结果
样例 1
输入
3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132
输出
2
13195
13
*/
const int N = 45010;
int a[N], b[N];
int n, mod,z;

long long fastmi(long long a, long long b, long long mod) {
	long long ret = 1;
	while (b != 0) {
		if (b & 1) { ret *= a; ret %= mod; }
		a = a * a % mod;
		b >>= 1;
	}

	return ret;
}


void solve() {
	cin >> mod;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	long long res = 0;
	for (int i = 0; i < n; i++) {
		res += fastmi(a[i], b[i], mod);
		res %= mod;
	}
	cout << res << endl;
	return;
}

int main()
{
	cin >> z;
	while (z--) {
		solve();
	}

	return 0;
}

 